// 使用已建立的 next 指针
// 第一种情况是连接同一个父节点的两个子节点，它们可以通过同一个节点直接访问到
// 第二种情况是不同父亲的子节点直接建立连接
// 第 N 层节点直接建立 next 指针后，再建立第 N + 1 层节点的 next 指针，可以通过 next 指针访问
// 同一层的所有结点

var connect = function (root) {
  if (root == null) return root;
  let leftmost = root;
  while (leftmost.left != null) {
    let head = leftmost;
    while (head != null) {
      head.left.next = head.right;
      if (head.next != null) {
        head.right.next = head.next.left;
      }
      head = head.next;
    }
    leftmost = leftmost.left;
  }
  return root;
};

// 它与下一道题最大的区别是完全二叉树与二叉树，
// 完全二叉树意味着子树不可能出现（只有右子树而没有左子树）的情况

var connect = function (root) {
  if (!root) return null;
  let queue = [root];
  while (queue.length) {
    let len = queue.length;
    while (len--) {
      let node = queue.shift();
      if (len == 0) {
        node.next = null;
      } else {
        node.next = queue[0];
      }
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
  }
  return root;
};
